import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

/**
 * @author minasora
 * @date 2019/10/8 14:38
 * @description 染色体类，可以通过split函数和Solution类进行转化
 * 一条染色体对应一个解，一个解由多个Route路径组成
 * 染色体中的每个基因位都代表一个客户序号
 */
public class Chromosome {
    final int INF = 999999;
    ArrayList<Integer> cur_list; // 染色体的编码，其中的基因位为每个客户点的序号
    double fitness = 0; // 适应度

    /**
     * 构造函数，随机生成一个初始的染色体，这个染色体中的基因序列是随机的
     */
    Chromosome() {
        cur_list = new ArrayList<>();
        for (int i = 1; i <= Conf.N; i++) {
            this.cur_list.add(i);
        }
        Collections.shuffle(this.cur_list); // 打乱列表顺序，做到随机生成
        cur_list.add(0, 0); // 从仓库出发
    }

    /**
     * 解码（Chromosome->Solution）
     * 使用bellman-ford算法分割染色体为多条路径，这多条路径即是解
     * 使用分割函数：跑一遍bellman-ford算法获得最优分割，就可以得到该染色体对应的解，实际上转化为从开始点到结束点的最短路划分问题
     * 用split方法切割染色体得到的一定是，此染色体对应的解
     *
     * @return
     */
    Solution toSolution() {
        Solution solution = new Solution();

        int j; // 循环的标识（后面会用到）
        int cost;// 载量花费
        double time;// 消耗的时间

        // 相当于：原点到此点的距离
        // 距离数组，其中每一个元素表示，在染色体的基因位序列中，该元素前面所有的基因位序列代表的城市一共消耗的时间
        double[] V = new double[Conf.N + 1];
        for (int i = 1; i <= Conf.N; i++) // 初始化为最大值
            V[i] = INF;

        // 存储索引位置点的前驱节点（即此节点所在路径中，最前面的客户节点，从仓库出发最先到达的客户节点）
        int[] P = new int[Conf.N + 1];
        for (int i = 1; i <= Conf.N; i++) { // 初始化路径中每个点的前一个点，最开始所有点都是单独存在
            P[i] = this.cur_list.get(i);
        }

        // Bellman-Ford算法在图论中应用是：在有负权的有向图中，找到出发点到所有点的最短路径
        // 下面是Bellman-Ford算法对染色体的基因序列进行分割
        // 将每个基因位看作是一个节点，得到的图片必定为图中所示。
        // 求这种图的最短路可以从左向右，依次求从当前点出发到后面各点的最短路，每求一次即相当于用当前点为后面的点松弛一次。
        for (int i = 1; i <= Conf.N; i++) { // 利用i点为i点后面的所有点进行松弛操作
            cost = 0;
            time = 0;
            j = i;
            while (true) {
                // 1.计算：仓库 -> cur_list.get(i) -> ... -> cur_list.get(j) -> 仓库，的最短路径的cost和time
                if (i == j)
                {
                    // 仓库 -> cur_list.get(j) -> 仓库
                    // 计算：这一段路程花费的时间
                    time += Math.max(Conf.customers[cur_list.get(j)].r_time, Conf.dis_matriax[0][cur_list.get(j)]);// 最早到达时间
                    time += Conf.customers[cur_list.get(j)].s_time; // 服务时长
                    time += Conf.dis_matriax[cur_list.get(j)][0]; // 路上花费的时间
                    // 计算：这一段路程的载量
                    cost += Conf.customers[cur_list.get(j)].demand;
                } else {
                    // 仓库 -> cur_list.get(i) -> ... -> cur_list.get(j - 1) -> cur_list.get(j) -> 仓库
                    // 计算：这一段路程花费的时间
                    double next_time = time - Conf.dis_matriax[cur_list.get(j - 1)][0] + Conf.dis_matriax[cur_list.get(j)][cur_list.get(j - 1)];
                    // 如果不满足时间窗约束，则跳出循环
                    if (next_time > Conf.customers[cur_list.get(j)].d_time)
                        break;
                    time = Math.max(next_time, Conf.customers[cur_list.get(j)].r_time);
                    time += Conf.dis_matriax[cur_list.get(j)][0];
                    // 计算：这一段路程的载量
                    cost += Conf.customers[cur_list.get(j)].demand;
                }

                // 2.更新V[]和P[]
                if (cost <= Conf.Cap) { // 假如满足容量约束
                    if (V[cur_list.get(j)] > V[cur_list.get(i - 1)] + time) { // 且当前得到的到cur_list.get(j)的路径优于其他路径
                        // 则不断更新到达cur_list.get(j)客户点的最短路
                        V[cur_list.get(j)] = V[cur_list.get(i - 1)] + time;
                        P[cur_list.get(j)] = this.cur_list.get(i - 1);
                    }
                    j++;
                }

                // 3.判断是否满足：仓库时间窗约束、载量约束、遍历完毕
                if (j > Conf.N || time >= Conf.customers[0].d_time || cost >= Conf.Cap)
                    break;
            }
        }
        Route route = new Route();

        // 从后往前开始捯
        int tmp = P[cur_list.get(Conf.N)]; // 从最后面的基因位开始
        int i = Conf.N; // 染色体基因位的索引
        // 将分割过的染色体重新组成Solution
        while (i > 0) {
            // 如果这些基因位的前置节点都是tmp，则他们同属一条独立的路径
            if (P[cur_list.get(i)] == tmp)
                route.cus_list.add(cur_list.get(i));
            else { // 如果这些基因位的前置节点发生了改变，则表明开启了新的路径
                route.getValue(); // 计算路径的路程
                Collections.reverse(route.cus_list); // 反转路径中的客户序列
                solution.rou_list.add(route); // 添加路径进入解
                tmp = P[cur_list.get(i)];
                route = new Route();
                route.cus_list.add(cur_list.get(i));
            }
            i--;
        }
        if (route.cus_list.size() != 0) {
            Collections.reverse(route.cus_list);
            route.getValue();
            solution.rou_list.add(route);
        }
        return solution;
    }

    //当前染色体的复制
    Chromosome copy() {
        Chromosome chromosome = new Chromosome();
        chromosome.cur_list.clear();
        chromosome.cur_list.addAll(this.cur_list);
        return chromosome;
    }

    //设置fitness
    void setFitness() {
        this.fitness = this.toSolution().getFitness();
    }
}
